﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _15_ThreeSum
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nums = { -1, 0, 1, 2, -1, -4 };

            IList<IList<int>> result = ThreeSum(nums);

            foreach (List<int> list in result)
            {
                Console.WriteLine(list.ToString());
            }
            Console.ReadLine();
        }

        private static IList<IList<int>> ThreeSum(int[] nums)
        {
            IList<IList<int>> res = new List<IList<int>>();

            List<int> numSet = nums.ToList();
            numSet.Sort();

            for (int i = 0; i < numSet.Count - 2; i++)
            {
                if (i == 0 || (i > 0 && numSet[i] != numSet[i - 1]))
                {
                    int lo = i + 1, hi = numSet.Count - 1, sum = 0 - numSet[i];
                    while (lo < hi)
                    {
                        if (numSet[lo] + numSet[hi] == sum)
                        {
                            res.Add(new List<int>() { numSet[i], numSet[lo], numSet[hi] });
                            while (lo < hi && numSet[lo] == numSet[lo + 1]) lo++;
                            while (lo < hi && numSet[hi] == numSet[hi - 1]) hi--;
                            lo++; hi--;
                        }
                        else if (numSet[lo] + numSet[hi] < sum) lo++;
                        else hi--;
                    }
                }
            }

            return res;
        }
    }
}
